package cloud.lysky.java.on.datastruct_and_algorithm.day00002;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * @author luoly
 * @describe
 * @date 2023-07-27 21:39
 **/
// 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
public class Solution {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(4);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        int[] result = reversePrint3(head);
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i]);
        }
    }

    // 解法1: 通过遍历链表两次，第一次计算链表长度，第二次将值存入数组
    public static int[] reversePrint(ListNode head) {
        ListNode temp = head;
        // 1.计算链表长度，找到尾节点即为数组长度
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        int[] result = new int[length];
        // 再遍历一次链表，将值存入数组
        temp = head;
        while (temp != null) {
            result[length - 1] = temp.val;
            length--;
            temp = temp.next;
        }
        return result;
    }

    // 解法2：递归
    public static int[] reversePrint2(ListNode head) {
        List<Integer> result = new ArrayList<>();
        recursion(head, result);
        // 列表转数组
        return result.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void recursion(ListNode head, List<Integer> result) {
        if (head == null) {
            return;
        }
        recursion(head.next, result);
        result.add(head.val);
    }

    // 解法3：巧妙使用栈结构，先进后出
    public static int[] reversePrint3(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode temp = head;
        // 遍历链表，将值存入栈中
        while (temp != null) {
            stack.push(temp.val);
            temp = temp.next;
        }
        int[] ints = new int[stack.size()];
        // 遍历栈，将值存入数组
        for (int i = 0; i < ints.length; i++) {
            ints[i] = stack.pop();
        }
        return ints;
    }
}
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
